package com.zyong.heap;
/**
 * 程序的问题：已知数组a[n],求数组b[n].要求：b[i]=a[0]*a[1]*……*a[n-1]/a[i]，不能用除法。
a.时间复杂度O(n),空间复杂度O(1)。 b.除了迭代器i,不允许使用任何其它变量（包括栈临时变量等）
 * @author yong.zhang
 *
 */
public class Tencent2012 {
	static int N = 3;
	public static void main(String[] args) {
		//这个解法把a数组里面的数据修改了，如果下次要用，就不行了。
	        int [] a  = new int[N];
			int [] b = new int[N];
			int i;
	        for(i = 0; i < N; i++){
	               a[i] = i + 1;
	        }
	        b[0] = 1;
	        for(i = 1; i < N; i++){
	               b[i] = b[i - 1] * a[i - 1];
	        }
	       
	        for(i = N - 2; i > 0; i--){
	               a[i] = a[i + 1] * a[i];
	        }
	       
	        for(i = 0; i < N - 1; i++){
	               b[i] = b[i] * a[i + 1];
	               System.out.printf("%d ", b[i]);
	        }
	      System.out.println("\n"); 
	      
	      test2();
	}
	//解法二：
	 public static void test2() {
	        int[] a = new int[N];
	        int[] b = new int[N];
	        for (int i = 0; i < N; i++) {
	            a[i] = i + 4;
	        }

	        b[0] = 1;
	        for (int i = 1; i < N; i++) {
	        
	            
	            b[i] = b[i - 1] * a[i - 1];
	        }
	        /**
             * b[i] = a[0]a[1]a[2]...a[i-1]a[i+1]a[i+2]....a[N-2]a[N-1]
             * 分成两段看   a[0]a[1]a[2]...a[i-1]     a[i+1]a[i+2]....a[N-2]a[N-1]
             * 分开计算
             * 通过循环可以得知 下面两行代码等于
             *       b[0] = b[0]*a[i-1];
                     b[i] = b[0];
             *  eq ： b[i] = b[i - 1] * a[i - 1];
             */
	       /* for (int i = 0; i < N; i++) {
	       
                b[0] = b[0]*a[i-1];
                b[i] = b[0];
            }*/

	        for (int i = N - 2; i > 0; i--) {
	            b[0] *= a[i + 1];
	            b[i] *= b[0];
	        }
	        b[0] *= a[1];
	        for (int i = 0; i < N; i++) {
	            System.out.printf("%d ", b[i]);
	        }
	        System.out.println("\n"); 
	        for (int i =0;i<a.length;i++) {
	            System.out.println("a["+i+"] =" + a[i] ); 
            }
	    }
}
